package com.heima.leetcode.practice;

import java.util.Map;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 53 最大子数组和
 * @date 2024/12/17 10:46
 */
public class E53 {

    /**
     * <h3>方法一： Kadane's Algorithm，动态规划的一种应用，效率最快</h3>
     *
     * @param nums 数组
     * @return 最大子数组和
     */
    public int maxSubArray1(int[] nums) {
        // maxLocal是以当前元素为结尾的最大连续子数组和
        int maxGlobal = nums[0], maxLocal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxLocal = Math.max(nums[i], maxLocal + nums[i]);
            maxGlobal = Math.max(maxGlobal, maxLocal);
        }
        return maxGlobal;
    }

    /*
        // [-2, 1,-3, 4,-1, 2, 1,-5, 4]   nums[]
        // [-2, 1,-2, 4, 3, 5, 6, 1, 5]   dp[]

        其中dp[i]表示的是以i结尾的连续子数组的最大和
    */

    /**
     * <h3>方法二：动态规划，效率第二</h3>
     *
     * @param nums 数组
     * @return 最大子数组和
     */
    public int maxSubArray2(int[] nums) {
        // 1. 定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。
        int[] dp = new int[nums.length];
        // 2. 初始化 dp 数组，将第一个元素设为 nums[0]，max设置为 nums[0]。
        int max = nums[0];
        dp[0] = nums[0];
        // 3. 遍历数组，计算 dp 数组。
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            max = Math.max(max, dp[i]);
        }
        // 4. 返回 dp 数组中的最大值。
        return max;
    }

    /**
     * <h3>方法三：分治，效率最差</h3>
     * @param nums 数组
     * @return 最大子数组和
     */
    public int maxSubArray3(int[] nums) {
        return findMaxSubArray(nums, 0, nums.length - 1);
    }

    /**
     * 分治实现
     * @param nums 数组
     * @param begin 左边界（包含）
     * @param end 右边界（包含）
     * @return 当前范围最大子数组和
     */
    private int findMaxSubArray(int[] nums, int begin, int end) {
        // 1. 递归终止条件
        if(begin == end) return nums[begin];
        // 2. 递归计算左右子数组的最大和
        int median = (begin + end) >>> 1;
        int leftMax = findMaxSubArray(nums, begin, median);
        int rightMax = findMaxSubArray(nums, median + 1, end);
        // 3. 计算跨中间的最大和
        int crossMax = findCrossMax(nums, begin, median, end);
        // 4. 返回左右子数组的和中较大的一个
        return Math.max(crossMax, Math.max(leftMax, rightMax));
    }

    /**
     * 跨中间的最大和
     * @param nums 数组
     * @param begin 左边界（包含）
     * @param median 中间值
     * @param end 右边界（包含）
     * @return 跨中间的最大和
     */
    private int findCrossMax(int[] nums, int begin, int median, int end) {
        // 1. 计算左边最大和
        int leftMax = Integer.MIN_VALUE, leftSum = 0;
        for (int i = median; i >= begin; i--){
            leftSum += nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        // 2. 计算右边最大和
        int rightMax = Integer.MIN_VALUE, rightSum = 0;
        for (int i = median + 1; i <= end; i++){
            rightSum += nums[i];
            rightMax = Math.max(rightMax, rightSum);
        }
        // 3. 返回跨中间的最大和
        return leftMax + rightMax;
    }
}
